package interview;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Node{
    Node left;
    Node right;
    int val;

    public Node(int val) {
        this.val = val;
    }
}

public class TreeTest {

    public static void main(String[] args) {
        Node par1 = new Node(1);
        Node par3 = new Node(3);
        Node par5 = new Node(5);
        Node par4 = new Node(4);
        Node par6 = new Node(6);
        Node par7 = new Node(7);
        Node par9 = new Node(9);

        par4.left = par6;
        par4.right = par7;
        par6.left = par1;
        par6.right = par9;
        par9.left = par3;
        par9.right = par5;

//        List<Integer> solution = solution(par4);
//        solution.stream().forEach(System.out::println);

        beforePrint(par4);
    }

    public static void beforePrint(Node node){
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || node != null){
            while(node != null){
                System.out.println(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;

        }
    }

    public static void printTree(Node node){
        if(node != null){
            System.out.println(node.val);
            printTree(node.left);
            printTree(node.right);
        }
    }


    public static List<Integer> solution(Node root){
        List<Integer> list = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.isEmpty()){
            while (root != null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                root = root.right;
            }
        }
        return list;
    }

}
